\documentclass[a4paper]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}

%%\usepackage{algorithm}
%%\usepackage{algorithmic}

%%%%%%%%%% marges %%%%%%%%%%

%%\usepackage{layout}
\usepackage[top=3cm, bottom=3cm, left=4cm, right=4cm]{geometry}



\begin{document}
\title{Parallélisation d'un code pré-existant de lancer de rayons}

\author{Guillaume \bsc{Boutin}, Cyrille \bsc{Piacibello}}

\maketitle

\section*{Introduction}
L'objectif de ce projet est de paralléliser un code pré-existant de
lancer de rayons. Nous ne nous intéresserons pas à l'algorithme de
dessin, nous nous contenterons d'utiliser la fonction qui calcul la
valeur de chaque pixel.  La difficulté de cette parallélisation est le
fait que les valeurs de certains pixels sont beaucoup plus difficiles à
calculer que d'autres. En effet, cela dépend du fichier scène en entrée.

La problématique ici est donc celle de l'ordonnancement.

\section{Premières proposition d'ordonnancement}
Dans cette partie, nous allons expliquer les différentes approches
envisageables.

On pourrait imaginer d'attribuer aux processus les pixels un par
un. Cette solution permettrait de répartir très finement les taches
sur les processus. Néanmoins, pour des raisons de temps d'accés
mémoire, nous avons tout intérêt à attribuer à chaque processus des
données contiguës en mémoires.

\subsection{Répartition du travail régulière}
Soit P*Q le nombre de processus utilisé. Une façon intuitive de
répartir le travail est de découper l'image à créer en une grille de
P*Q. Le processus (i,j) traitera le bloc (i,j). Cette répartition des
taches est très grossière, puisque les processus en charge d'une
région dans laquelle il n'y aura que peu d'objets finiront très vite
leur travail. On obtient donc un speed up très mauvais.

\subsection{Répartition en utilisant des blocs plus petits}
Le fait de limiter la taille des blocs à 8*8 permet à chaque processus
de travailler plusieurs régions différentes de l'image.  Le choix des
zones assignées à chaque processus est crucial, pour éviter de
reproduire l'erreur de l'approche précédente. Pour répartir de façon
équilibrée les blocs de chaque processus sur toute l'image, une
solution est d'appliquer le théorème des restes chinois : Ce théorème
est le suivant : Soit $n_{1}$, $n_{2}$ ... $n_{p}$ p nombres entiers
premiers entres eux deux à deux. Soit $n =\prod_{k=1}^p n_{k}$. Alors
pour toute famille de d'entiers $(a_{i})_{0<i<p+1}$, il existe un
unique $x$ (unique modulo $n$) tel que : $\forall{i}$ ($0<i<p+1$)
$\Rightarrow x\equiv a_{i}$ (mod $n_{i}$).  

Nous allons utilisez cette propriété de la façon suivante : Soit C le
nombre de blocs, on choisit un entier N premier avec C.  On attribue
ensuite au processus i les blocs tels que : $ bloc(i) = (j\times
N)\%C)$ pour $i*q-1<j<min((i+1)*q-1,C-1)$.  Cette répartition est plus
efficace puisque plus régulière, mais dans certians cas particuliers,
elle peut ne pas fonctionner très bien. Par exemple, sur nos machines,
la différence entre le thread le plus rapide et le thread le plus lent
était de 10 secondes sur l'exemple Pyramide 2.

\section{Utilisation d'un système de vol de travail}
Naturellement, toutes les implémentations où la répartitions des blocs
sur les processus est faite à l'avance ne peuvent pas être
satisfaisantes, puisqu'on ignore la structure de l'image qui va être
produite. Nous allons maintenant présenter une implémentation
attribuant les taches dynamiquement aux processus.

\subsection{Principe de l'algorithme}
Nous allons utiliser une méthode dite de vol de travail. À chaque
processus est attribuée une liste de blocs à traiter. Pour cette
répartition, nous avons réutilisé la méthode utilisant le théorème des
restes chinois. Ensuite, dès qu'un processus n'a plus de travail, il
demande aux autres des tâches pas encore effectuée.


\subsubsection{Protocole de communication}
Les processus sont organisé en un anneau. Chaque processus connait le
rang de son successeur et de son prédécesseur.  

Lorsqu'un processus n'a plus de travail, il effectue une demande de
travail à son successeur, puis attend une réponse.

Lorsqu'un processus reçoit une demande de travail, plusieurs cas sont
possibles :
\begin{itemize}
\item Si il a du travail, il renvoi alors la tâche au demandeur, et
  l'enlève de sa liste de tâche.
\item Si il n'a pas non plus de travail, il fait suivre la demande à
  son successeur.
\end{itemize}
Chaque demande est signée, afin que chaque processus sache à qui
renvoyer du travail lorsqu'il reçoit une demande qu'il peut
satisfaire. De plus, le fait que les messages soient signés permet de
détecter quand il n'y a plus de travail disponible dans l'anneau. En
effet, lorsqu'un processus reçoit une demande de travail, il vérifie
si l'emetteur n'est pas lui-même. Si c'est le cas, cela signifit qu'il
n'y a plus de travail disponible dans l'anneau.

La terminaison est un vrai problème, car on doit garantir qu'aucun
processus ne fasse de demandes à un processus qui a déjà quitté.

Pour avoir cette propriété, nous avons défini le protocole de
terminaison suivant :
\begin{itemize}
\item Le processus p reçoit une demande de travail de sa part.
\item Il envoi alors un signal de terminaison à son successeur. Ce
  signal signifie qu'il n'y a plus de travail disponible.
\item Le successeur vérifie si il est l'emetteur du message, si c'est
  le cas, il termine.
\item si ce n'est pas le cas, il fait suivre le message à son
  successeur, puis termine.
\end{itemize}

De cette façon le dernier processus à quitter est celui qui a détecté
qu'il n'y avait plus de travail. Si deux processus sont dans ce cas,
le protocole fonctionne toujours car les processus en question ne
quitteront que lorsqu'ils recevront le message de terminaison de
l'autre, ce qui garantit qu'aucun processus n'enverra de message à un
processus déjà terminé.

\subsection{Détails de l'implémentation}

Pour implémenter ce système, nous avons crée deux threads POSIX dans
chaque processus. Un thread sera chargé du calcul, et le second sera
chargé de l'attente de communications entrantes des autres processus.

Le thread principal se contente de créer les deux threads, puis il
attend leurs terminaisons avant d'effectuer la reduction du résultat.

\subsubsection{Thread de calcul}
Le thread de calcul pioche des tâches dans une liste. Celle-ci est
partagée entre les deux threads, protégée par un mutex. Lorsqu'il n'a
plus qu'une tâche, il vérifie la valeur d'une variable booléene
\verb?no_more_jobs?, protégée de même par un mutex, qui indique si il
y a encore du travail disponible quelque part. Si c'est le cas, il
effectue un MPI_Send pour demander du travail à son successeur. Il
finit ensuite la dernière tâche, puis se termine. Si ce n'est pas le
cas, cela signifie que la tâche restante est la dernière qu'il
effectuera, il quitte donc dès qu'elle est terminée.

\subsubsection{Thread de communication}
Ce thread est continuellement en train de recevoir des messages dans
un buffer. ce buffer esst constitué de 2 entiers. Le premier
représente le type de message, le second contient le rang du processus
à l'origine du message, sauf dans le cas particulier ou le message est
une tâche, dans ce cas la provenance de la tâche n'est pas importante
et on stocke donc à cet endroit le numéro de la tache à effectuer.  Il
y a 3 types de messages différenciés selon la valeur du premier
élément du buffer : 
\begin{itemize}
\item 0 : c'est une demande standard de travail, le second élément du
  buffer est l'adresse du processus en manque de travail.
\item 2 : c'est un travail, le second élément est le numéro de la
  tâche. On crée à nouveau le thread de travail, qui va effectuer la
  tâche.
\item 1 : c'est un signal de terminaison. Cela signifie qu'une demande
  de travail n'a été satisfaite par personne, et a été reçue par son
  propriétaire. Le numéro du processus en question est le second
  élément du buffer.
\end{itemize}

Chaque type de message entraîne un comportement qui dépend de la
valeur du second élément du buffer : 
\begin{itemize}
\item Dans le cas d'une demande travail : si elle provient de
  soi-même, on met la variable \verb?no_more_jobs? à vrai, puis on
  envoi un signal de terminaison. Si elle provient d'un autre
  processus et que l'on peut y répondre, on dépile une tâche de sa
  propre liste de tâche pour l'envoyer au processeur dans le besoin.
  Enfin, dans le dernier cas, on fait simplement suivre la demande au
  processus suivant en recopiant dans le buffer d'envoi les valeurs du
  buffer de reception.
\item Dans le cas d'un signal de terminaison : Si il provient de
  soi-même, cela signifie que le processus enquestion est le dernier
  processus vivant. Il peut donc terminer directement. Si il provient
  d'un autre processus, on peut en déduire qu'aucune demande de
  travail ne sera plus satisfaite. On met donc la variable
  \verb?no_more_jobs? à vrai, puis on fait suivre le signal de
  terminaison tel quel, et on quitte.
\end{itemize}

Pour permettre une exécution concurrente de requête MPI, nous avons
initialisé nos communications avec la fonction MPI_Init_thread(), et
l'argument MPI_THREAD_MULTIPLE, qui permet d'avoir plus d'un thread
chargé des communications. Ici notre utilisation de cette propriété a
été minimal, dans le sens où les communications autorisées au thread
de calcul sont réduites.

\section{Résultats}
Nous avons tout d'abord validé l'algorithme de vol de travail à
travers une implémentation simpliste, faisant néanmoins intervenir les
mêmes mécanismes et fonctions que la version définitive. En parallèle,
nous avons effectué la version de repartition des blocs grâce au
théorème des restes chinois.  

Enfin nous avons fusionné les deux codes pour obtenir une
implémentation efficace du lancer de rayon.


\section*{Conclusion}
Ce projet est notre première occasion de mélanger une approche mémoire
partagée avec les threads POSIX et une approche communication à
travers la bibliothèque MPI. Nus avons pu nous consacrer completement
aux problématiques de parallélisme, car le code pré-existant
fonctionnait très bien.


\end{document}
